A general architecture of a shared storage-forward switch chip is as illustrated in FIG. 1.
A process of forwarding a data frame by the shared storage-forward switch chip mainly includes the following three steps: receiving and buffering a data frame, forwarding data, and transmitting the data frame and reclaiming a buffer.
Receiving and buffering a data frame: a data frame entering the chip from an external port is buffered into a shared buffer 2 via an input interface 1. The shared buffer 2 is generally a RAM (Random Access Memory). An allocation of the data frame to the shared buffer is managed by a buffer manager 4 using a buffer address pointer. In a subsequent procedure of forwarding the data frame, the body of the data frame will be held in the shared buffer 2 all the time, and only the buffer address pointer will be transferred in the chip. Only after a forwarding instruction is issued and reaches an output interface 3, the output interface 3 reads out the data frame from the shared buffer 2 in accordance with the buffer address pointer, and transmits the data frame to an external port.
Forwarding data: when the data frame is written into the shared buffer 2, the input interface 1 extracts from the data frame the information for forwarding the data frame, and the information together with the buffer address pointer of the data frame is transmitted to a data forwarding channel 5. The data forwarding channel 5 performs forwarding and searching operations on the received information for forwarding so as to obtain a destination port for the data frame, and transmits the buffer address pointer together with information on destination port to the output port 3.
Transmitting the data frame and reclaiming a buffer: the output interface 3 reads out the data frame from the shared buffer 2 in accordance with the buffer address pointer transmitted from the data forwarding channel 5, and transmits the data frame to an external output port in accordance with the information on destination port for the data frame, The buffer manager 4 reclaims the corresponding buffer.
In the above process, the buffer manager 4 manages the allocation and reclaiming of a buffer address pointer of the shared buffer mainly through the following two methods.
One method is to use a FIFO (First In First Out) mode to perform management on allocation and reclaiming of a buffer address pointer of a shared buffer.
Specifically, a FIFO queue is used to hold all idle buffer address pointers of a shared buffer. Each FIFO element in the FIFO queue stores one idle buffer address pointer. The depth of the FIFO queue shall be equal to the total number of the buffer elements in the shared buffer, so that buffer address pointers of all the buffer elements can be stored when all the buffer elements of the shared buffer are idle. A “FIFO read address” is used to indicate the first available idle buffer address pointer in the shared buffer, and a “FIFO write address” is used to indicate a FIFO element where a reclaimed buffer address pointer shall be stored. When the buffer manager 4 allocates a buffer address pointer to the data frame, an idle buffer address pointer is read out in accordance with a “FIFO read address”, and the number of idle buffer address pointers in the FIFO queue is decremented by one. When the data frame stored in the buffer is transmitted to the external port, and the buffer address pointer needs to be reclaimed, the buffer address pointer is written into a FIFO element in accordance with a “FIFO write address”, and the number of idle buffer address pointers in the FIFO queue is incremented by one.
The FIFO queue can be implemented with a RAM. If the total number of buffer elements in a shared buffer is 2m, an m×2m bit RAM is needed for implementation of the FIFO queue. In other words, if the total number of buffer elements in a shared buffer is 8 K, the FIFO queue shall be a RAM of 13 bits×8 K=104 Kbits, with 13 bits of the RAM on average consumed for each buffer element.
When a system is reset, an initial status of the FIFO queue is as illustrated in FIG. 2.
In FIG. 2, assuming that the total number of the buffer elements is 8 K, when the system is reset, none of the buffer elements in the shared buffer stores a data frame. Consequently, all the 8 K buffer address pointers shall be stored in the FIFO queue. At this time, the FIFO is in a “full” status, and the “FIFO read address” is identical to that of the “FIFO write address”, both of which are zero.
A FIFO queue during a normal operation is as illustrated in FIG. 3.
In FIG. 3, assuming that a next allocatable buffer address pointer indicated by the “FIFO read address” is stored in a FIFO element with an address of 90 in the FIFO queue, and a next reclaimed buffer address pointer indicated by the “FIFO write address” shall be written into a FIFO element with an address of 56 in the FIFO queue. At this time, the total number of the available buffer address pointers stored in the FIFO queue is 8 K-(90-56).
With the use of this method for management of the shared buffer, a buffer address pointer can be allocated or reclaimed just through one access to the FIFO queue, thus resulting in a powerful capability in allocating and reclaiming the shared buffer and a high efficiency in management of the shared buffer. However, because both the width and the depth of the FIFO queue increase dramatically as the number of the buffer elements in the shared buffer increases, RAM resource consumed for management of each buffer element will increase dramatically. Consequently, this method is not suitable for a switch chip with a shared buffer of a relatively large storage space.
The other method is to use a bitmap table and a FIFO mode for management on the allocation and reclaiming of a buffer address pointer of the shared buffer.
The bitmap table is a two-dimensional table, and each buffer address pointer corresponds to 1 bit in the bitmap table. The bitmap table can be implemented with a RAM.
A common mapping relationship between a buffer address pointer and a bitmap table is that upper n bits of the buffer address pointer are used as a row address in the bitmap table, and lower m bits of the buffer address pointer are used as a column address in the bitmap table. A bit in the bitmap table, determined together by the row and column addresses, when being 1, indicates that a corresponding buffer address pointer has been occupied, and when being 0, indicates that the corresponding buffer address pointer is idle. It may take many clock cycles if an idle buffer address pointer is searched for directly in the bitmap table, and therefore, a small FIFO queue may be used in combination for management of buffer address pointers.
Specifically, some idle buffer address pointers of the shared buffer are preset in a FIFO queue, and two threshold values are set for the FIFO, where one is a search threshold value, i.e. a lower threshold value, and the other is a reclaim threshold value, i.e. an upper filed value. When an idle buffer address pointer stored in the FIFO exceeds the reclaim threshold value, the buffer address pointer above the reclaim threshold value is returned to the bitmap table, and the corresponding bit in the bitmap table is set as 0. When an idle buffer address pointer stored in the FIFO is below the search threshold value, some idle buffer address pointers are searched out automatically from the bitmap table, and are stored into the FIFO, and the corresponding bits in the bitmap table are set as 1.
With the use of this method for management of buffer address pointers, when the system is reset, an initial status of the bitmap table is as illustrated in FIG. 4.
In FIG. 4, the total number of the buffer elements in the shared buffer is 8 K, and the bitmap table has a size of (28×25) bits. Because the buffer address pointers of 0-31 are stored in the FIFO queue, the bits in the bitmap table, which are corresponding to these buffer address pointers, are set as “1”.
A bitmap table during a normal operation is as illustrated in FIG. 5.
In the bitmap table of FIG. 5, the buffer address pointer corresponding to a bit of “1” has been occupied, and a buffer address pointer corresponding to a bit of “0” has not been occupied. Here, the cases in which a buffer address pointer is occupied include: a case in which this buffer address pointer is an idle buffer address pointer, and is stored in the FIFO, or a case in which the buffer element corresponding to this buffer address pointer has been occupied with a data frame.
In allocation of a buffer address pointer, the buffer address pointer is read out from a FIFO in accordance with the “FIFO read address”, and the total number of the buffer address pointers stored in the FIFO is decremented by one. In reclaiming of a buffer address pointer, the reclaimed buffer address pointer is written into the FIFO in accordance with the “FIFO write address”, and the total number of the buffer address pointers stored in the FIFO is incremented by one.
Normally, this method can achieve that a buffer address pointer is allocated or reclaimed in one clock cycle, thus alleviating the speed problem of direct searching for an idle buffer pointer in the bitmap table. However, if the total number of buffer address pointers allocated or reclaimed sequentially exceeds the depth of the FIFO, making the FIFO reach a limit status, it shall be required to have a direct read or write access to the bitmap table, and consequently, the efficiency in the access to an buffer address pointer may be degraded greatly.
With the use of this method for management of the shared buffer, RAM resource consumed for management of each buffer element is 1 bit, and does not vary with the number of the buffer elements, with low resources being consumed. However, this method may not be steady in time consumption in searching for an idle buffer address pointer, and may be of a weak capability in allocating and reclaiming a buffer address pointer especially when the FIFO is in a limit status, and therefore results in a greatly reduced efficiency in management of the shared buffer. This method may not be suitable for a switch chip with a relatively large exchange bandwidth.